package m202406.d24;

import java.util.ArrayList;
import java.util.List;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/6/24 12:35
 */
public class Q1631 {

    public static void main(String[] args) {
        Q1631 q1631 = new Q1631();
        int i = q1631.minimumEffortPath(new int[][]{
                {1, 2, 2},
                {3, 8, 2},
                {5, 3, 5}
        });
        System.out.println(i);
    }

    public int minimumEffortPath(int[][] heights) {
        int n = heights.length;
        int m = heights[0].length;
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int c = i * m + j;
                if (j < m - 1) {
                    edges.add(new Edge(c, c + 1, Math.abs(heights[i][j] - heights[i][j + 1])));
                }
                if (i < n - 1) {
                    edges.add(new Edge(c, c + m, Math.abs(heights[i][j] - heights[i + 1][j])));
                }
            }
        }
        edges.sort((a, b) -> a.weight - b.weight);
        UF uf = new UF(m * n);
        for (Edge edge : edges) {
            uf.union(edge.p1, edge.p2);
            if (uf.isConnect(0, m * n - 1)) {
                return edge.weight;
            }
        }
        return 0;
    }

    private static class UF {
        private int[] data;

        public UF(int size) {
            this.data = new int[size];
            for (int i = 0; i < data.length; i++) {
                this.data[i] = i;
            }
        }

        public void union(int x, int y) {
            int xr = find(x);
            int yr = find(y);
            if (xr == yr) {
                return;
            }
            this.data[xr] = yr;
        }

        public boolean isConnect(int x, int y) {
            return find(x) == find(y);
        }

        public int find(int x) {
            while (x != this.data[x]) {
                x = this.data[x];
            }
            return x;
        }

    }

    private static class Edge {
        private int p1;
        private int p2;
        private int weight;

        public Edge(int p1, int p2, int weight) {
            this.p1 = p1;
            this.p2 = p2;
            this.weight = weight;
        }
    }
}
